package com.shiguiwu.springmybatis.algorithm.sort;

import java.util.Arrays;

/**
 * @description: 插入排序
 * 分别初始化一个有序和无序列表，讲无序加到有序中
 * @author: stone
 * @date: Created by 2021/3/16 20:13
 * @version: 1.0.0
 * @pakeage: com.shiguiwu.springmybatis.algorithm.sort
 */
public class InsertSort extends AbstractSort implements Sort{

    public static void main1(String[] args) {
        int[] init = SortTests.init(80000);
        Sort sort =  UseTimeSortProxy.createProxy(new InsertSort(init), Sort.class);
        sort.sort();
        System.out.println(Arrays.toString(init));

    }
    public InsertSort(int[] array) {
        super(array);
    }

    @Override
    public void sort() {
        int len = array.length;
        for (int i = 1; i < len; i++) {
            //待插入的数据
            int insertVal = array[i];
            //i的前面的一个索引
            int insertIndex = i - 1;
            //给insertVal找位置
            //1,insertIndex >= 0 为了数组不越界 2,insertVal < array[insertIndex]还没有找到位置，继续
            //3,继续将insterIndex后移,即有序列表要后移，准备给待插入的数，腾出位置
            while (insertIndex >= 0 && insertVal < array[insertIndex]) {
                array[insertIndex + 1] = array[insertIndex];
                insertIndex--;
            }
            //4,已经找到位置了，加到前一个位置上去,如果遍历就是最大的，就直接下一个循环，也不用交换
            if (insertIndex + 1 != i) {
                array[insertIndex + 1] = insertVal;
            }
        }
    }
}
